package hot100;

import java.lang.annotation.RetentionPolicy;
import java.util.*;

/**
 * hot100
 */
public class Solution {

    /**
     * 1. 两数之和
     *
     * @param nums
     * @param target
     * @return
     */
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        int[] result = new int[2];
        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(target - nums[i])) {
                result[0] = map.get(target - nums[i]);
                result[1] = i;
                return result;
            }
            map.put(nums[i], i);
        }

        return result;
    }

    /**
     * 49. 字母异位词分组
     * HashMap + 排序(每个字符串排序后变为key)
     *
     * @param strs
     * @return
     */
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<>();

        for (String str : strs) {
            char[] array = str.toCharArray();
            Arrays.sort(array);
            String key = new String(array);

            if (!map.containsKey(key)) {
                map.put(key, new ArrayList<>());
            }

            map.get(key).add(str);
        }

        return new ArrayList<>(map.values());
    }

    /**
     * 128. 最长连续序列
     * 使用HashSet先遍历一遍去重，然后只检查当前num是序列的起点的情况，即不存在Set中不存在num - 1
     *
     * @param nums
     * @return
     */
    public int longestConsecutive(int[] nums) {
        Set<Integer> numSet = new HashSet<>();
        for (int num : nums) {
            numSet.add(num);
        }

        int result = 0;

        for (int num : numSet) {
            if (!numSet.contains(num - 1)) {
                int currentNum = num;
                int currentStreak = 1;

                while (numSet.contains(currentNum + 1)) {
                    currentNum++;
                    currentStreak++;
                }

                result = Math.max(result, currentStreak);
            }
        }

        return result;
    }

    // 双指针 TODO

    /**
     * 283. 移动零
     *
     * @param nums
     */
    public void moveZeroes(int[] nums) {
        for (int i = 0, j = 0; j < nums.length; j++) {
            if (nums[j] != 0) {
                int temp = nums[i];
                nums[i] = nums[j];
                nums[j] = temp;
                i++;
            }
        }
    }

    /**
     * 11. 盛最多水的容器
     * 初始化两个指针，分别指向数组的两端，每次循环指向较短柱子的指针向内移动
     *
     * @param height
     * @return
     */
    public int maxArea(int[] height) {
        int i = 0, j = height.length - 1;
        int result = 0;

        while (i < j) {
            int cur = Math.min(height[i], height[j]) * (j - i);
            result = Math.max(result, cur);
            if (height[i] > height[j]) {
                j--;
            } else {
                i++;
            }
        }

        return result;
    }

    /**
     * 15. 三数之和
     * 遍历数组，i + 1为left n - 1为right，去重，如果满足和为0也要去重
     *
     * @param nums
     * @return
     */
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(nums);
        int n = nums.length;

        for (int i = 0; i < n - 2; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            int left = i + 1, right = n - 1;
            while (left < right) {
                int cur = nums[left] + nums[right] + nums[i];
                if (cur < 0) {
                    left++;
                } else if (cur > 0) {
                    right--;
                } else {
                    List<Integer> path = new ArrayList<>();
                    path.add(nums[i]);
                    path.add(nums[left]);
                    path.add(nums[right]);
                    result.add(path);
                    while (left < right && nums[left] == nums[left + 1]) left++;
                    while (left < right && nums[right] == nums[right - 1]) right--;
                    left++;
                    right--;
                }
            }
        }
        return result;
    }

    /**
     * 42. 接雨水
     * 设置leftMax 和 rightMax保存左右分别的最大值
     * 每次left right值更小的位置向内缩，如果该值cur大于当前左（右）最大值，更新最大值，否则result += max - cur
     *
     * @param height
     * @return
     */
    public int trap(int[] height) {
        int left = 0, right = height.length - 1, result = 0;
        int leftMax = 0, rightMax = 0;

        while (left < right) {
            if (height[left] < height[right]) {
                if (height[left] > leftMax) {
                    leftMax = height[left];
                } else {
                    result += leftMax - height[left];
                }
                left++;
            } else {
                if (height[right] > rightMax) {
                    rightMax = height[right];
                } else {
                    result += rightMax - height[right];
                }
                right--;
            }
        }

        return result;
    }

    // 滑动窗口 TODO

    /**
     * 3. 无重复字符的最长子串·
     * Set + 左右指针
     *
     * @param s
     * @return
     */
    public int lengthOfLongestSubstring(String s) {
        if (s.length() == 0) return 0;

        Set<Character> set = new HashSet<>();
        int left = 0, result = 1;
        set.add(s.charAt(0));

        for (int i = 1; i < s.length(); i++) {
            char cur = s.charAt(i);
            if (!set.contains(cur)) {
                result = Math.max(result, i - left + 1);
            } else {
                while (left < i && set.contains(cur)) {
                    set.remove(s.charAt(left));
                    left++;
                }
            }
            set.add(cur);
        }

        return result;
    }

    /**
     * 438. 找到字符串中所有字母异位词
     * Set（计数数组） + 滑动窗口（左右指针）
     *
     * @param s
     * @param p
     * @return
     */
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> result = new ArrayList<>();
        if (s.length() < p.length()) {
            return result;
        }
        int[] countS = new int[26];
        int[] countP = new int[26];

        for (char ch : p.toCharArray()) {
            countP[ch - 'a']++;
        }

        int left = 0;

        for (int i = 0; i < p.length(); i++) {
            char cur = s.charAt(i);
            countS[cur - 'a']++;
        }

        if (Arrays.equals(countS, countP)) {
            result.add(left);
        }

        for (int i = p.length(); i < s.length(); i++) {
            countS[s.charAt(i) - 'a']++;
            countS[s.charAt(left) - 'a']--;
            left++;
            if (Arrays.equals(countS, countP)) {
                result.add(left);
            }
        }
        return result;
    }

    // 子串 TODO

    /**
     * 560. 和为 K 的子数组
     * 前缀和sum + HashMap
     * 逆向思维，将问题转为寻找满足 sum[j] - sum[i] = k 的索引对(i,j)，再转为寻找当前前缀和sum - k在Map中存在的次数
     *
     * @param nums
     * @param k
     * @return
     */
    public int subarraySum(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, 1);
        int sum = 0, count = 0;

        for (int num : nums) {
            sum += num;
            if (map.containsKey(sum - k)) {
                count += map.get(sum - k);
            }

            map.put(sum, map.getOrDefault(sum, 0) + 1);
        }

        return count;
    }

    /**
     * 239. 滑动窗口最大值
     * 双端队列Deque 存坐标
     *
     * @param nums
     * @param k
     * @return
     */
    public int[] maxSlidingWindow(int[] nums, int k) {
        int[] result = new int[nums.length - k + 1];
        Deque<Integer> deque = new ArrayDeque<>();

        for (int i = 0; i < nums.length; i++) {
            if (!deque.isEmpty() && i - deque.peek() >= k) {
                deque.poll();
            }

            while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
                deque.pollLast();
            }

            deque.offer(i);

            if (i >= k - 1) {
                result[i - k + 1] = nums[deque.peek()];
            }
        }

        return result;
    }

    /**
     * 76. 最小覆盖子串
     * 滑动窗口 + HashMap
     *
     * @param s
     * @param t
     * @return
     */
    public String minWindow(String s, String t) {
        int[] map = new int[128];
        for (char ch : t.toCharArray()) {
            map[ch]++;
        }
        int count = t.length();
        int left = 0, right = 0, result = Integer.MAX_VALUE, minLeft = 0;

        while (right < s.length()) {
            // 1.增加当前字符
            char rChar = s.charAt(right);
            if (map[rChar] > 0) {
                count--;
            }
            map[rChar]--;
            right++;

            // 2.缩小左边界
            while (count == 0) {
                if (result > right - left) {
                    // 这里right更新过因此长度不需要再+1
                    result = right - left;
                    minLeft = left;
                }

                char lChar = s.charAt(left);
                if (map[lChar] == 0) {
                    count++;
                }
                map[lChar]++;
                left++;
            }
        }

        return result == Integer.MAX_VALUE ? "" : s.substring(minLeft, minLeft + result);
    }

    // 普通数组 TODO

    /**
     * 53. 最大子数组和
     *
     * @param nums
     * @return
     */
    public int maxSubArray(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        dp[0] = nums[0];
        int result = dp[0];
        for (int i = 1; i < n; i++) {
            dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);
            result = Math.max(result, dp[i]);
        }

        return result;
    }

    /**
     * 56. 合并区间
     * 贪心
     *
     * @param intervals
     * @return
     */
    public int[][] merge(int[][] intervals) {
        if (intervals.length == 1) {
            return intervals;
        }
        List<int[]> result = new ArrayList<>();
        Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));

        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i][0] <= intervals[i - 1][1]) {
                intervals[i][0] = intervals[i - 1][0];
                intervals[i][1] = Math.max(intervals[i - 1][1], intervals[i][1]);
            } else {
                result.add(intervals[i - 1]);
            }
        }

        return result.toArray(new int[result.size()][2]);
    }

    /**
     * 189. 轮转数组
     * 1.三次反转（最优解，空间复杂度为O（1））
     * 2. 新建一个数组，下标 + k 后 取模 数组长度，为轮转结果的新数组的下标
     *
     * @param nums
     * @param k
     */
    public void rotate(int[] nums, int k) {
        int n = nums.length;
        k = k % n;
        reverse(nums, 0, n - 1);
        reverse(nums, 0, k - 1);
        reverse(nums, k, n - 1);
    }

    private void reverse(int[] nums, int left, int right) {
        while (right < nums.length && left < right) {
            int temp = nums[left];
            nums[left] = nums[right];
            nums[right] = temp;
            left++;
            right--;
        }
    }

    /**
     * 238. 除自身以外数组的乘积
     * 分别计算当前位置的左右部分的乘积
     *
     * @param nums
     * @return
     */
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] result = new int[n];
        result[0] = 1;

        // 计算左边乘积
        for (int i = 1; i < n; i++) {
            result[i] = result[i - 1] * nums[i - 1];
        }

        int right = 1;

        for (int i = n - 1; i >= 0; i--) {
            result[i] *= right;
            right *= nums[i];
        }

        return result;
    }

    /**
     * 41. 缺失的第一个正数
     * 利用坐标和值的对应关系，如果坐标为值-1的位置不为当前值，将每个值换到坐标为值-1的位置
     *
     * @param nums
     * @return
     */
    public int firstMissingPositive(int[] nums) {
        int n = nums.length;

        for (int i = 0; i < n; i++) {
            while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
                swap(nums, i, nums[i] - 1);
            }
        }

        for (int i = 0; i < n; i++) {
            if (i + 1 != nums[i]) {
                return i + 1;
            }
        }

        return n + 1;
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    // 矩阵 TODO

    /**
     * 73. 矩阵置零
     * 定义两个数组，长度分别为m、n，用于标记该行（列）是否有0
     * 优化：只需要定义两个变量来标记第一行、第一列是否有0，然后用第一行、第一列来当作上面的数组进行标记，处理其他部分，最后再处理第一行、第一列
     *
     * @param matrix
     */
    public void setZeroes(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        boolean row = false;
        boolean col = false;
        for (int i = 0; i < m; i++) {
            if (matrix[i][0] == 0) {
                col = true;
                break;
            }
        }

        for (int i = 0; i < n; i++) {
            if (matrix[0][i] == 0) {
                row = true;
                break;
            }
        }

        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (matrix[i][j] == 0) {
                    matrix[i][0] = 0;
                    matrix[0][j] = 0;
                }
            }
        }

        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (matrix[i][j] != 0 && (matrix[i][0] == 0 || matrix[0][j] == 0)) {
                    matrix[i][j] = 0;
                }
            }
        }

        if (row) {
            for (int i = 0; i < n; i++) {
                matrix[0][i] = 0;
            }
        }

        if (col) {
            for (int i = 0; i < n; i++) {
                matrix[i][0] = 0;
            }
        }
    }

    /**
     * 54. 螺旋矩阵
     * 最后判断相等条件，可能会没遍历到的一行或一列
     *
     * @param matrix
     * @return
     */
    public List<Integer> spiralOrder(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        int top = 0, bottom = m - 1, left = 0, right = n - 1;
        List<Integer> result = new ArrayList<>();
        while (top < bottom && left < right) {
            for (int i = left; i < right; i++) {
                result.add(matrix[top][i]);
            }
            for (int i = top; i < bottom; i++) {
                result.add(matrix[i][right]);
            }
            for (int i = right; i > left; i--) {
                result.add(matrix[bottom][i]);
            }
            for (int i = bottom; i > top; i--) {
                result.add(matrix[i][left]);
            }
            top++;
            left++;
            bottom--;
            right--;
        }
        if (left == right && top == bottom) {
            result.add(matrix[top][left]);
        } else if (left == right) {
            for (int i = top; i <= bottom; i++) {
                result.add(matrix[i][left]);
            }
        } else if (top == bottom) {
            for (int i = left; i <= right; i++) {
                result.add(matrix[top][i]);
            }
        }
        return result;
    }

    /**
     * 48. 旋转图像
     * 转置 + 每一行翻转
     *
     * @param matrix
     */
    public void rotate(int[][] matrix) {
        int n = matrix.length;
        //1. 转置(列变行，行变列)
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = temp;
            }
        }

        //2. 每一行分别翻转
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n / 2; j++) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[i][n - j - 1];
                matrix[i][n - j - 1] = temp;
            }
        }
    }

    /**
     * 240. 搜索二维矩阵 II
     * 从右上角开始搜索
     *
     * @param matrix
     * @param target
     * @return
     */
    public boolean searchMatrix2(int[][] matrix, int target) {
        int i = 0;
        int j = matrix[0].length - 1;

        while (i < matrix.length && j >= 0) {
            if (target > matrix[i][j]) {
                i++;
            } else if (target < matrix[i][j]) {
                j--;
            } else {
                return true;
            }
        }

        return false;

    }

    // 链表 TODO

    /**
     * 160. 相交链表
     * 遍历到null后切换遍历到另一个链表，直到两个指针相等时遍历结束，返回。
     *
     * @param headA
     * @param headB
     * @return
     */
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode curA = headA, curB = headB;

        while (curA != curB) {
            curA = (curA == null) ? headB : curA.next;
            curB = (curB == null) ? headA : curB.next;
        }

        return curA;
    }

    /**
     * 206. 反转链表
     * 定义prev用于反转
     *
     * @param head
     * @return
     */
    public ListNode reverseList(ListNode head) {
        ListNode prev = null, cur = head;

        while (cur != null) {
            ListNode next = cur.next;
            cur.next = prev;
            prev = cur;
            cur = next;
        }

        return prev;
    }

    /**
     * 234. 回文链表
     * 快慢指针找到中间节点，反转后半段链表，与前半段比较
     *
     * @param head
     * @return
     */
    public boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null) return true;
        ListNode slow = head, fast = head;

        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        ListNode prev = null, next = null;
        while (slow != null) {
            next = slow.next;
            slow.next = prev;
            prev = slow;
            slow = next;
        }

        // 3. 比较前后两部分
        ListNode p1 = head;

        while (p1 != null && prev != null) {
            if (p1.val != prev.val) {
                return false;
            }
            p1 = p1.next;
            prev = prev.next;
        }

        return true;
    }

    /**
     * 142. 环形链表 II
     *
     * @param head
     * @return
     */
    public ListNode detectCycle(ListNode head) {
        if (head == null || head.next == null) return null;

        ListNode slow = head, fast = head;

        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                break;
            }
        }

        if (slow == fast) {
            slow = head;
            while (slow != fast) {
                slow = slow.next;
                fast = fast.next;
            }
            return slow;
        }

        return null;
    }

    /**
     * 21. 合并两个有序链表
     *
     * @param list1
     * @param list2
     * @return
     */
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode dummy = new ListNode(-1);
        ListNode cur = dummy;

        while (list1 != null && list2 != null) {
            if (list1.val < list2.val) {
                cur.next = list1;
                list1 = list1.next;
            } else {
                cur.next = list2;
                list2 = list2.next;
            }
            cur = cur.next;
        }

        if (list1 != null) {
            cur.next = list1;
        } else if (list2 != null) {
            cur.next = list2;
        }

        return dummy.next;
    }

    /**
     * 2. 两数相加
     * 判null放到内部
     *
     * @param l1
     * @param l2
     * @return
     */
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(-1);
        ListNode cur = dummy;
        int plus = 0;
        while (l1 != null || l2 != null) {
            int x = (l1 != null) ? l1.val : 0;
            int y = (l2 != null) ? l2.val : 0;
            int sum = x + y + plus;
            plus = sum / 10;
            ListNode node = new ListNode(sum % 10);
            cur.next = node;
            cur = cur.next;
            if (l1 != null) l1 = l1.next;
            if (l2 != null) l2 = l2.next;
        }

        if (plus != 0) {
            ListNode node = new ListNode(plus);
            cur.next = node;
        }

        return dummy.next;
    }

    /**
     * 19. 删除链表的倒数第 N 个结点
     *
     * @param head
     * @param n
     * @return
     */
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode slow = dummy.next, fast = dummy.next;
        while (n-- > 0) {
            fast = fast.next;
        }
        if (fast == null) {
            return slow.next;
        }
        while (fast.next != null) {
            slow = slow.next;
            fast = fast.next;
        }
        slow.next = slow.next.next;
        return dummy.next;
    }

    /**
     * 24. 两两交换链表中的节点
     *
     * @param head
     * @return
     */
    public ListNode swapPairs(ListNode head) {
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode cur = dummy;

        while (cur.next != null && cur.next.next != null) {
            ListNode first = cur.next;
            ListNode second = cur.next.next;

            first.next = second.next;
            second.next = first;
            cur.next = second;

            cur = first;
        }

        return dummy.next;
    }

    /**
     * 25. K 个一组翻转链表
     * 循环内部分割begin, end,end为需要翻转的最后一个节点的next
     *
     * @param head
     * @param k
     * @return
     */
    public ListNode reverseKGroup(ListNode head, int k) {
        if (k == 1) return head;

        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode prev = dummy;

        while (prev.next != null) {
            ListNode begin = prev.next;
            ListNode end = prev.next;
            int count = 0;
            while (end != null && count < k) {
                end = end.next;
                count++;
            }
            if (count < k) return dummy.next;

            prev.next = reverse(begin, end);
            begin.next = end;
            prev = begin;
        }
        return dummy.next;
    }

    private ListNode reverse(ListNode begin, ListNode end) {
        ListNode prev = null, cur = begin;
        while (cur != end) {
            ListNode next = cur.next;
            cur.next = prev;
            prev = cur;
            cur = next;
        }

        return prev;
    }

    /**
     * 138. 随机链表的复制
     *
     * @param head
     * @return
     */
    public Node copyRandomList(Node head) {
        if (head == null) return null;
        Node cur = head;
        while (cur != null) {
            Node newNode = new Node(cur.val);
            newNode.next = cur.next;
            cur.next = newNode;
            cur = newNode.next;
        }

        cur = head;
        while (cur != null) {
            if (cur.random != null) {
                cur.next.random = cur.random.next;
            }
            cur = cur.next.next;
        }

        cur = head;
        Node dummy = new Node(-1);
        Node newCur = dummy;
        while (cur != null) {
            newCur.next = cur.next;
            cur.next = cur.next.next;
            newCur = newCur.next;
            cur = cur.next;
        }

        return dummy.next;
    }

    /**
     * 148. 排序链表
     * 归并排序
     *
     * @param head
     * @return
     */
    public ListNode sortList(ListNode head) {
        return sortList(head, null);
    }

    private ListNode sortList(ListNode head, ListNode tail) {
        if (head == null) {
            return null;
        }
        if (head.next == tail) {
            head.next = null;
            return head;
        }
        ListNode slow = head, fast = head;
        while (fast != tail && fast.next != tail) {
            slow = slow.next;
            fast = fast.next.next;
        }

        ListNode list1 = sortList(head, slow);
        ListNode list2 = sortList(slow, tail);

        return merge(list1, list2);
    }

    private ListNode merge(ListNode p1, ListNode p2) {
        ListNode dummy = new ListNode(-1);
        ListNode cur = dummy;
        while (p1 != null && p2 != null) {
            if (p1.val < p2.val) {
                cur.next = p1;
                p1 = p1.next;
            } else {
                cur.next = p2;
                p2 = p2.next;
            }
            cur = cur.next;
        }
        if (p1 != null) {
            cur.next = p1;
        } else if (p2 != null) {
            cur.next = p2;
        }

        return dummy.next;
    }

    /**
     * 23. 合并 K 个升序链表
     * 堆排序，直接建小根堆，每次将array[0]的元素出队列
     *
     * @param lists
     * @return
     */
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) return null;
        List<ListNode> list = new ArrayList<>();
        for (ListNode node : lists) {
            if (node != null) {
                list.add(node);
            }
        }

        ListNode[] nodes = list.toArray(new ListNode[0]);
        int size = nodes.length;
        buildHeap(nodes, size);

        ListNode dummy = new ListNode(-1);
        ListNode cur = dummy;

        while (size > 0) {
            cur.next = nodes[0];
            cur = cur.next;
            if (nodes[0].next == null) {
                nodes[0] = nodes[size - 1];
                size--;
            } else {
                nodes[0] = nodes[0].next;
            }
            heapify(nodes, size, 0);
        }
        return dummy.next;
    }

    private void buildHeap(ListNode[] nodes, int size) {
        for (int i = size / 2 - 1; i >= 0; i--) {
            heapify(nodes, size, i);
        }
    }

    private void heapify(ListNode[] nodes, int size, int i) {
        int min = i;
        int left = 2 * i + 1;
        int right = 2 * i + 2;

        if (left < size && nodes[left].val < nodes[min].val) {
            min = left;
        }
        if (right < size && nodes[right].val < nodes[min].val) {
            min = right;
        }

        if (min != i) {
            swap(nodes, min, i);
            heapify(nodes, size, min);
        }
    }

    private void swap(ListNode[] nodes, int i, int j) {
        ListNode temp = nodes[i];
        nodes[i] = nodes[j];
        nodes[j] = temp;
    }

    // 树 TODO

    /**
     * 101. 对称二叉树，镜像二叉树
     *
     * @param root
     * @return
     */
    public boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return true;
        }
        return isSymmetricHelper(root.left, root.right);
    }

    public boolean isSymmetricHelper(TreeNode left, TreeNode right) {
        if (left == null && right == null) {
            return true;
        }
        if (left == null || right == null) {
            return false;
        }
        if (left.val != right.val) {
            return false;
        }

        return isSymmetricHelper(left.left, right.right) && isSymmetricHelper(left.right, right.left);
    }

    /**
     * 543. 二叉树的直径
     * 最后结果要减一
     *
     * @param root
     * @return
     */
    public int diameterOfBinaryTree(TreeNode root) {
        maxDeep(root);
        return result - 1;
    }

    private int maxDeep(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftHeight = maxDeep(root.left);
        int rightHeight = maxDeep(root.right);
        result = Math.max(result, leftHeight + rightHeight + 1);
        return Math.max(leftHeight, rightHeight) + 1;
    }

    /**
     * 108. 将有序数组转换为二叉搜索树
     *
     * @param nums
     * @return
     */
    public TreeNode sortedArrayToBST(int[] nums) {
        int n = nums.length;
        return generate(nums, 0, n - 1);
    }

    private TreeNode generate(int[] nums, int begin, int end) {
        if (begin > end) {
            return null;
        }
        int mid = (begin + end) / 2;
        TreeNode root = new TreeNode(nums[mid]);
        root.left = generate(nums, begin, mid - 1);
        root.right = generate(nums, mid + 1, end);

        return root;
    }

    public long prev = Long.MIN_VALUE;

    /**
     * 98. 验证二叉搜索树
     * 设一个prev变量记录前面的值，不需要判断大于小于，只需要中序遍历递增就行，也就是只需要判断当前节点小于prev节点
     *
     * @param root
     * @return
     */
    public boolean isValidBST(TreeNode root) {
        if (root == null) {
            return true;
        }
        if (!isValidBST(root.left)) {
            return false;
        }
        if (root.val <= prev) {
            return false;
        }
        prev = root.val;
        if (!isValidBST(root.right)) {
            return false;
        }
        return true;
    }

    /**
     * 199. 二叉树的右视图
     * 层序
     *
     * @param root
     * @return
     */
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) return result;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            while (size > 0) {
                TreeNode cur = queue.poll();
                if (size == 1) {
                    result.add(cur.val);
                }
                if (cur.left != null) {
                    queue.offer(cur.left);
                }
                if (cur.right != null) {
                    queue.offer(cur.right);
                }
                size--;
            }
        }

        return result;
    }

    /**
     * 114. 二叉树展开为链表
     * 先序遍历构造链表再遍历链表构造树
     *
     * @param root
     */
    public void flatten(TreeNode root) {
        if (root == null) {
            return;
        }
        List<TreeNode> path = new ArrayList<>();
        preorder(root, path);

        TreeNode prev = root;
        for (int i = 1; i < path.size(); i++) {
            prev.left = null;
            prev.right = path.get(i);
            prev = path.get(i);
        }
    }

    private void preorder(TreeNode root, List<TreeNode> path) {
        if (root == null) return;

        path.add(root);
        preorder(root.left, path);
        preorder(root.right, path);
    }

    // 原地修改，每次找到cur左子树的最右节点，将这颗树接到cur的右边
    public void flatten2(TreeNode root) {
        TreeNode curr = root;
        while (curr != null) {
            if (curr.left != null) {
                // 找到左子树的最右节点
                TreeNode predecessor = curr.left;
                while (predecessor.right != null) {
                    predecessor = predecessor.right;
                }

                // 将右子树接到前驱节点的右边
                predecessor.right = curr.right;
                // 将左子树移到右子树位置
                curr.right = curr.left;
                curr.left = null;
            }
            // 处理下一个节点
            curr = curr.right;
        }
    }

    Map<Integer, Integer> map;

    /**
     * 105. 从前序与中序遍历序列构造二叉树
     *
     * @param preorder
     * @param inorder
     * @return
     */
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        map = new HashMap<>();
        int len = preorder.length;
        for (int i = 0; i < len; i++) {
            map.put(inorder[i], i);
        }
        return findNode(preorder, 0, inorder, 0, len - 1);
    }

    private TreeNode findNode(int[] preorder, int preBegin, int[] inorder, int inBegin, int inEnd) {
        if (inBegin > inEnd) {
            return null;
        }
        TreeNode root = new TreeNode(preorder[preBegin]);
        int index = map.get(preorder[preBegin]);

        root.left = findNode(preorder, preBegin + 1, inorder, inBegin, index - 1);
        root.right = findNode(preorder, preBegin + (index - inBegin) + 1, inorder, index + 1, inEnd);

        return root;
    }

    /**
     * 106. 从中序与后序遍历序列构造二叉树
     *
     * @param inorder
     * @param postorder
     * @return
     */
    public TreeNode buildTree2(int[] inorder, int[] postorder) {
        map = new HashMap<>();
        int len = inorder.length;
        for (int i = 0; i < len; i++) {
            map.put(inorder[i], i);
        }

        return findNode(inorder, 0, len - 1, postorder, len - 1);
    }

    private TreeNode findNode(int[] inorder, int inBegin, int inEnd, int[] postorder, int postEnd) {
        if (inBegin > inEnd || postEnd < 0) {
            return null;
        }
        TreeNode root = new TreeNode(postorder[postEnd]);
        int index = map.get(postorder[postEnd]);

        root.left = findNode(inorder, inBegin, index - 1, postorder, postEnd - (inEnd - index) - 1);
        root.right = findNode(inorder, index + 1, inEnd, postorder, postEnd - 1);

        return root;
    }

    Map<Long, Integer> sumMap = new HashMap<>();

    /**
     * 437. 路径总和 III
     * dfs, 前缀和，逆向思维，求cur - targetSum出现次数
     *
     * @param root
     * @param targetSum
     * @return
     */
    public int pathSum(TreeNode root, int targetSum) {
        if (root == null) {
            return 0;
        }
        sumMap.put(0L, 1);
        return dfs(root, 0L, targetSum);
    }

    private int dfs(TreeNode root, Long curSum, int targetSum) {
        if (root == null) {
            return 0;
        }
        curSum += root.val;
        int result = sumMap.getOrDefault(curSum - targetSum, 0);
        sumMap.put(curSum, sumMap.getOrDefault(curSum, 0) + 1);

        result += dfs(root.left, curSum, targetSum);
        result += dfs(root.right, curSum, targetSum);

        sumMap.put(curSum, sumMap.get(curSum) - 1);
        return result;
    }

    /**
     * 236. 二叉树的最近公共祖先
     * 分别向left,right寻找是否有p或者q节点
     *
     * @param root
     * @param p
     * @param q
     * @return
     */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return null;
        }
        if (root == p || root == q) {
            return root;
        }

        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);

        if (left != null && right != null) {
            return root;
        } else if (left == null) {
            return right;
        }

        return left;
    }

    public int result = Integer.MIN_VALUE;

    /**
     * 124. 二叉树中的最大路径和
     * 后序遍历
     *
     * @param root
     * @return
     */
    public int maxPathSum(TreeNode root) {
        helper(root);
        return result;
    }

    private int helper(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftSum = Math.max(helper(root.left), 0);
        int rightSum = Math.max(helper(root.right), 0);
        int curSum = root.val + leftSum + rightSum;

        result = Math.max(curSum, result);
        return Math.max(leftSum, rightSum) + root.val;
    }

    // TODO 图论

    /**
     * 200. 岛屿数量
     *
     * @param grid
     * @return
     */
    public int numIslands(char[][] grid) {
        int result = 0;
        int m = grid.length;
        int n = grid[0].length;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '1') {
                    result++;
                    dfs(grid, i, j);
                }
            }
        }

        return result;
    }

    private void dfs(char[][] grid, int i, int j) {
        if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] != '1') {
            return;
        }

        grid[i][j] = '0';

        dfs(grid, i - 1, j);
        dfs(grid, i + 1, j);
        dfs(grid, i, j - 1);
        dfs(grid, i, j + 1);
    }

    /**
     * 994. 腐烂的橘子
     *
     * @param grid
     * @return
     */
    public int orangesRotting(int[][] grid) {
        int freshCount = 0;
        int result = 0;
        int m = grid.length, n = grid[0].length;
        Queue<int[]> queue = new LinkedList<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    freshCount++;
                } else if (grid[i][j] == 2) {
                    queue.offer(new int[]{i, j});
                }
            }
        }

        int[][] directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

        while (!queue.isEmpty() && freshCount > 0) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int[] cur = queue.poll();
                for (int[] direct : directions) {
                    int x = cur[0] + direct[0];
                    int y = cur[1] + direct[1];
                    if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 1) {
                        freshCount--;
                        grid[x][y] = 2;
                        queue.offer(new int[]{x, y});
                    }
                }
            }
            result++;
        }

        return freshCount == 0 ? result : -1;
    }

    /**
     * 207. 课程表
     * 拓扑排序 层序遍历
     *
     * @param numCourses
     * @param prerequisites
     * @return
     */
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        List<List<Integer>> adj = new ArrayList<>();
        int[] inDegree = new int[numCourses];
        for (int i = 0; i < numCourses; i++) {
            adj.add(new ArrayList<>());
        }

        for (int[] pre : prerequisites) {
            adj.get(pre[1]).add(pre[0]);
            inDegree[pre[0]]++;
        }

        Queue<Integer> queue = new LinkedList<>();
        int visit = 0;
        for (int i = 0; i < numCourses; i++) {
            if (inDegree[i] == 0) {
                queue.offer(i);
            }
        }

        while (!queue.isEmpty()) {
            int cur = queue.poll();
            visit++;
            for (int neighbor : adj.get(cur)) {
                if (--inDegree[neighbor] == 0) {
                    queue.offer(neighbor);
                }
            }
        }

        return visit == numCourses;
    }

    // 回溯 TODO

    List<String> res = new ArrayList<>();
    String[] numString = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    StringBuilder stringBuilder = new StringBuilder();

    /**
     * 17. 电话号码的字母组合
     *
     * @param digits
     * @return
     */
    public List<String> letterCombinations(String digits) {
        if (digits == null || digits.length() == 0) {
            return res;
        }
        dfs(digits, 0);
        return res;
    }

    private void dfs(String digits, int index) {
        if (index == digits.length()) {
            res.add(stringBuilder.toString());
            return;
        }
        String curString = numString[digits.charAt(index) - '0'];
        for (int i = 0; i < curString.length(); i++) {
            stringBuilder.append(curString.charAt(i));
            dfs(digits, index + 1);
            stringBuilder.deleteCharAt(stringBuilder.length() - 1);
        }
    }

    public boolean[][] visit;

    /**
     * 79. 单词搜索
     * 通过一个visit来标记已经使用过的位置，找到遍历能匹配第一个字符的位置再dfs
     *
     * @param board
     * @param word
     * @return
     */
    public boolean exist(char[][] board, String word) {
        int m = board.length, n = board[0].length;
        visit = new boolean[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == word.charAt(0)) {
                    if (dfs(board, word, 0, i, j)) {
                        return true;
                    }
                }

            }
        }

        return false;
    }

    private boolean dfs(char[][] board, String word, int index, int i, int j) {
        if (index == word.length()) {
            return true;
        }
        if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || board[i][j] != word.charAt(index) || visit[i][j]) {
            return false;
        }
        visit[i][j] = true;

        boolean result = dfs(board, word, index + 1, i - 1, j) || dfs(board, word, index + 1, i + 1, j) || dfs(board, word, index + 1, i, j - 1) || dfs(board, word, index + 1, i, j + 1);

        visit[i][j] = false;
        return result;
    }



    // 二分查找 TODO

    /**
     * 5. 搜索插入位置
     *
     * @param nums
     * @param target
     * @return
     */
    public int searchInsert(int[] nums, int target) {
        int i = 0, j = nums.length - 1;

        while (i <= j) {
            int mid = (i + j) / 2;
            if (nums[mid] < target) {
                i = mid + 1;
            } else if (nums[mid] > target) {
                j = mid - 1;
            } else {
                return mid;
            }
        }

        return i;
    }

    /**
     * 74. 搜索二维矩阵
     * 两次二分查找，先找在哪一行，再找target
     *
     * @param matrix
     * @param target
     * @return
     */
    public boolean searchMatrix(int[][] matrix, int target) {
        int left = 0, right = matrix.length - 1;

        while (left <= right) {
            int mid = (left + right) / 2;
            if (matrix[mid][0] < target) {
                left = mid + 1;
            } else if (matrix[mid][0] > target) {
                right = mid - 1;
            } else {
                return true;
            }
        }
        if (right < 0) {
            return false;
        }
        int row = right;
        left = 0;
        right = matrix[0].length - 1;

        while (left <= right) {
            int mid = (left + right) / 2;
            if (matrix[row][mid] < target) {
                left = mid + 1;
            } else if (matrix[row][mid] > target) {
                right = mid - 1;
            } else {
                return true;
            }
        }

        return false;
    }

    /**
     * 34. 在排序数组中查找元素的第一个和最后一个位置
     * 两次二分查找，区分判断条件，维护一个index变量；
     *
     * @param nums
     * @param target
     * @return
     */
    public int[] searchRange(int[] nums, int target) {
        int index = Integer.MAX_VALUE;
        int left = 0, right = nums.length - 1;
        int[] result = new int[]{-1, -1};
        while (left <= right) {
            int mid = (left + right) / 2;

            if (nums[mid] >= target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }

            if (nums[mid] == target) {
                index = Math.min(index, mid);
            }
        }

        if (index == Integer.MAX_VALUE) return result;

        result[0] = index;

        index = Integer.MIN_VALUE;
        left = 0;
        right = nums.length - 1;

        while (left <= right) {
            int mid = (left + right) / 2;

            if (nums[mid] <= target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }

            if (nums[mid] == target) {
                index = Math.max(index, mid);
            }
        }

        result[1] = index;

        return result;
    }

    /**
     * 33. 搜索旋转排序数组
     * 1.先看mid的左边有序还是右边有序
     * 2.再根据target是否在已知的有序区间中，改变left 或者 right的位置
     *
     * @param nums
     * @param target
     * @return
     */
    public int search(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return -1;
        }

        int left = 0, right = nums.length - 1;

        while (left <= right) {
            int mid = (left + right) / 2;

            if (nums[mid] == target) {
                return mid;
            }

            if (nums[left] <= nums[mid]) {
                if (nums[left] <= target && nums[mid] > target) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            } else {
                if (nums[right] >= target && nums[mid] < target) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }

        }

        return -1;
    }

    /**
     * 153. 寻找旋转排序数组中的最小值
     *
     * @param nums
     * @return
     */
    public int findMin(int[] nums) {
        int left = 0, right = nums.length - 1;

        while (left < right) {
            int mid = (left + right) / 2;
            if (nums[mid] > nums[right]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }

        return nums[left];
    }

    /**
     * 4. 寻找两个正序数组的中位数
     *
     * @param nums1
     * @param nums2
     * @return
     */
    public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        int total = m + n;
        int i = 0, j = 0;
        int prev = 0, curr = 0;

        for (int k = 0; k <= total / 2; k++) {
            prev = curr;
            if (i < m && (j >= n || nums1[i] <= nums2[j])) {
                curr = nums1[i++];
            } else {
                curr = nums2[j++];
            }
        }

        if (total % 2 == 1) {
            return curr;
        } else {
            return (prev + curr) / 2.0;
        }
    }

    // 栈 TODO

    /**
     * 20. 有效的括号
     *
     * @param s
     * @return
     */
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();

        for (Character ch : s.toCharArray()) {
            if (ch == '(' || ch == '{' || ch == '[') {
                stack.push(ch);
            } else {
                if (stack.isEmpty()) {
                    return false;
                }
                char ch2 = stack.peek();
                if (ch2 == '(' && ch == ')' || ch2 == '[' && ch == ']' || ch2 == '{' && ch == '}') {

                    stack.pop();

                } else {
                    return false;
                }
            }

        }

        return stack.isEmpty();
    }

    /**
     * 394. 字符串解码
     * 两个栈，一个存数字numStack，一个存字符strStack
     * 需要一个curSum来存当前数字，因为数字有可能不止1位；一个curStr来存当前的字符串
     * 当遍历到 ']'时，strStack出栈，并append n 次curStr，n为numStack出栈
     *
     * @param s
     * @return
     */
    public String decodeString(String s) {
        Stack<Integer> numStack = new Stack<>();
        Stack<String> strStack = new Stack<>();
        StringBuilder curStr = new StringBuilder();
        int curNum = 0;

        for (char ch : s.toCharArray()) {
            if (Character.isDigit(ch)) {
                curNum = curNum * 10 + (ch - '0');
            } else if (ch == '[') {
                numStack.push(curNum);
                curNum = 0;
                strStack.push(curStr.toString());
                curStr = new StringBuilder();
            } else if (ch == ']') {
                int num = numStack.pop();
                StringBuilder temp = new StringBuilder(strStack.pop());

                for (int i = 0; i < num; i++) {
                    temp.append(curStr);
                }
                curStr = temp;
            } else {
                curStr.append(ch);
            }
        }

        return curStr.toString();
    }

    /**
     * 739. 每日温度
     * 单调栈，使用Deque LinkedList效率会比Stack要高
     *
     * @param temperatures
     * @return
     */
    public int[] dailyTemperatures(int[] temperatures) {
        Deque<Integer> stack = new LinkedList<>();
        int n = temperatures.length;
        int[] result = new int[n];
        stack.push(0);
        for (int i = 1; i < n; i++) {
            while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
                int cur = stack.pop();
                result[cur] = i - cur;
            }
            stack.push(i);
        }

        return result;
    }

    /**
     * 84. 柱状图中最大的矩形
     * 这里的左边界应当是(i - deque.peek() - 1)而不是i - mid，为了能将符合条件但已经pop出去的坐标算进去
     * i - mid忽略了 left 可以向左扩展的情况
     * (i - deque.peek() - 1)找的才是左边第一个比当前i矮的柱子
     *
     * @param heights
     * @return
     */
    public int largestRectangleArea(int[] heights) {
        Deque<Integer> deque = new LinkedList<>();
        int result = 0;
        int[] newHeights = new int[heights.length + 2];
        System.arraycopy(heights, 0, newHeights, 1, heights.length);
        newHeights[0] = 0;
        newHeights[newHeights.length - 1] = 0;

        deque.push(0);
        for (int i = 1; i < newHeights.length; i++) {
            while (newHeights[i] < newHeights[deque.peek()]) {
                int mid = deque.pop();

                result = Math.max(result, (i - deque.peek() - 1) * newHeights[mid]);

            }
            deque.push(i);
        }

        return result;
    }

    // 堆 TODO

    /**
     * 347. 前 K 个高频元素
     * 手撕堆排序
     *
     * @param nums
     * @param k
     * @return
     */
    public int[] topKFrequent(int[] nums, int k) {
        // 1.统计频率
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        List<int[]> list = new ArrayList<>();

        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            list.add(new int[]{entry.getKey(), entry.getValue()});
        }
        int[][] array = list.toArray(new int[0][0]);

        // 2.堆排序
        maxHeapSort(array);
        int n = array.length;
        int[] result = new int[k];
        for (int i = 0; i < k; i++) {
            result[i] = array[n - k + i][0];
        }
        return result;
    }

    private void maxHeapSort(int[][] array) {
        int n = array.length;

        for (int i = n / 2 - 1; i >= 0; i--) {
            heapify(array, n, i);
        }

        for (int i = n - 1; i > 0; i--) {
            swap(array, i, 0);
            heapify(array, i, 0);
        }
    }

    private void heapify(int[][] array, int n, int i) {
        int largest = i;
        int left = 2 * i + 1;
        int right = 2 * i + 2;

        if (left < n && array[left][1] > array[largest][1]) {
            largest = left;
        }

        if (right < n && array[right][1] > array[largest][1]) {
            largest = right;
        }

        if (largest != i) {
            swap(array, i, largest);
            heapify(array, n, largest);
        }
    }

    private void swap(int[][] arr, int i, int j) {
        int[] temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    // 贪心算法 TODO

    /**
     * 121. 买卖股票的最佳时机
     *
     * @param prices
     * @return
     */
    public int maxProfit(int[] prices) {
        int cost = Integer.MAX_VALUE, result = 0;

        for (int price : prices) {
            cost = Math.min(cost, price);
            result = Math.max(result, price - cost);
        }

        return result;
    }

    /**
     * 55. 跳跃游戏
     *
     * @param nums
     * @return
     */
    public boolean canJump(int[] nums) {
        int jump = 0;
        for (int i = 0; i < nums.length; i++) {
            if (jump < i) {
                return false;
            }
            if (jump >= nums.length) {
                return true;
            }
            jump = Math.max(jump, i + nums[i]);
        }

        return true;
    }

    /**
     * 45. 跳跃游戏 II
     * 不关心具体跳到哪个位置，只关心范围
     * 1. 记录当前最大边界curEnd，可能到达最远位置farthest，跳跃次数result三个变量
     * 2. 当i到达curEnd时，result++，并将farthest赋给curEnd
     *
     * @param nums
     * @return
     */
    public int jump(int[] nums) {
        if (nums.length == 1) return 0;
        int result = 0, curEnd = 0, farthest = 0;

        for (int i = 0; i < nums.length; i++) {
            farthest = Math.max(farthest, i + nums[i]);

            if (i == curEnd) {
                result++;
                curEnd = farthest;
                if (farthest >= nums.length - 1) {
                    return result;
                }
            }

        }

        return result;
    }

    /**
     * 763. 划分字母区间
     * 1.用一个长度为26的数组，保存每个字符的最后出现的位置
     * 2.用一个变量target存放当前区别的字母中最大的边界值，遍历当 i == target时，存结果
     *
     * @param s
     * @return
     */
    public List<Integer> partitionLabels(String s) {
        List<Integer> result = new ArrayList<>();
        int[] edge = new int[26];

        for (int i = 0; i < s.length(); i++) {
            edge[s.charAt(i) - 'a'] = i;
        }

        int start = 0;
        int target = edge[s.charAt(0) - 'a'];

        for (int i = 0; i < s.length(); i++) {
            if (i == target) {
                result.add(i - start + 1);
                start = i + 1;
                if (i != s.length() - 1) {
                    target = edge[s.charAt(i + 1) - 'a'];
                }
                continue;
            }
            target = Math.max(target, edge[s.charAt(i) - 'a']);
        }

        return result;
    }

    // dp动态规划 TODO

    /**
     * 198. 打家劫舍
     *
     * @param nums
     * @return
     */
    public int rob(int[] nums) {
        int n = nums.length;
        if (n == 1) {
            return nums[0];
        }

        int[] dp = new int[n];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);

        for (int i = 2; i < n; i++) {
            dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
        }

        return Math.max(dp[n - 1], dp[n - 2]);
    }

    /**
     * 213. 打家劫舍 II
     * 分为从nums[0]开始 和 从nums[1]开始 两种情况
     *
     * @param nums
     * @return
     */
    public int rob2(int[] nums) {
        int n = nums.length;
        if (n == 1) {
            return nums[0];
        }
        return Math.max(robRange(nums, 0, n - 2), robRange(nums, 1, n - 1));
    }

    public int robRange(int[] nums, int start, int end) {
        if (start == end) {
            return nums[start];
        }
        int prevMax = nums[start];
        int curMax = Math.max(nums[start], nums[start + 1]);

        for (int i = start + 2; i <= end; i++) {
            int temp = curMax;
            curMax = Math.max(curMax, prevMax + nums[i]);
            prevMax = temp;
        }
        return curMax;
    }

    /**
     * 337. 打家劫舍 III
     * 后序遍历，用一个长度为2的dp数组来管理当前节点两种情况的最大金额
     * 情况1 dp[0] = 选当前root节点，那就不能选左右节点 root.val + left[1] + right[1]
     * 情况2 dp[1] = 不选，那就是左右节点分别的两种情况的最大值的和 Math.max(left[0], left[1]) + Math.max(right[0], right[1])
     *
     * @param root
     * @return
     */
    public int rob(TreeNode root) {
        int[] result = robHelper(root);
        return Math.max(result[0], result[1]);
    }

    private int[] robHelper(TreeNode root) {
        if (root == null) {
            return new int[]{0, 0};
        }

        int[] left = robHelper(root.left);
        int[] right = robHelper(root.right);

        return new int[]{root.val + left[1] + right[1], Math.max(left[0], left[1]) + Math.max(right[0], right[1])};
    }

    /**
     * 279. 完全平方数
     * 尝试 j*j <= i 的前提下的每个j
     *
     * @param n
     * @return
     */
    public int numSquares(int n) {
        int[] dp = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            dp[i] = i;
        }

        for (int i = 2; i <= n; i++) {
            for (int j = 1; j * j <= i; j++) {
                dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
            }
        }

        return dp[n];
    }

    /**
     * 322. 零钱兑换
     *
     * @param coins
     * @param amount
     * @return
     */
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, amount + 1);
        dp[0] = 0;

        for (int i = 0; i < coins.length; i++) {
            for (int j = coins[i]; j <= amount; j++) {
                dp[j] = Math.min(dp[j], dp[j - coins[i]] + 1);
            }
        }

        return dp[amount] > amount ? -1 : dp[amount];
    }

    /**
     * 139. 单词拆分
     * 完全背包
     *
     * @param s
     * @param wordDict
     * @return
     */
    public boolean wordBreak(String s, List<String> wordDict) {
        int n = s.length();
        boolean[] dp = new boolean[n + 1];
        dp[0] = true;
        for (int i = 1; i <= n; i++) {
            for (String cur : wordDict) {
                if (i >= cur.length() && dp[i - cur.length()] && s.startsWith(cur, i - cur.length())) {
                    dp[i] = true;
                    break;
                }
            }
        }

        return dp[n];
    }

    /**
     * 300. 最长递增子序列
     * 两层循环dp
     *
     * @param nums
     * @return
     */
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        Arrays.fill(dp, 1);
        int result = 1;
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            result = Math.max(result, dp[i]);
        }

        return result;
    }

    /**
     * 152. 乘积最大子数组
     * 由于要考虑负数，因此维护两个变量：当前最大值和当前最小值
     *
     * @param nums
     * @return
     */
    public int maxProduct(int[] nums) {
        int n = nums.length;
        int curMax = nums[0];
        int curMin = nums[0];
        int result = nums[0];


        for (int i = 1; i < nums.length; i++) {
            int temp = curMax;
            curMax = Math.max(nums[i], Math.max(nums[i] * curMax, nums[i] * curMin));
            curMin = Math.min(nums[i], Math.min(nums[i] * curMin, nums[i] * temp));

            result = Math.max(result, curMax);
        }

        return result;
    }

    /**
     * 416. 分割等和子集
     * 0-1背包问题，dp[j]一维倒序遍历，找所有当前能够凑成的和
     *
     * @param nums
     * @return
     */
    public boolean canPartition(int[] nums) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        if (sum % 2 == 1) return false;
        sum /= 2;
        int n = nums.length;
        boolean[] dp = new boolean[sum + 1];
        dp[0] = true;

        for (int num : nums) {
            for (int j = sum; j >= num; j--) {
                dp[j] = dp[j] || dp[j - num];
            }
            if (dp[sum]) return true;
        }

        return false;
    }

    /**
     * 62. 不同路径
     *
     * @param m
     * @param n
     * @return
     */
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];

        for (int i = 0; i < m; i++) {
            dp[i][0] = 1;
        }

        for (int j = 1; j < n; j++) {
            dp[0][j] = 1;
        }

        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }

        return dp[m - 1][n - 1];
    }

    /**
     * 64. 最小路径和
     *
     * @param grid
     * @return
     */
    public int minPathSum(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int[][] dp = new int[m][n];
        dp[0][0] = grid[0][0];
        for (int i = 1; i < m; i++) {
            dp[i][0] = dp[i - 1][0] + grid[i][0];
        }
        for (int j = 1; j < n; j++) {
            dp[0][j] = dp[0][j - 1] + grid[0][j];
        }

        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
            }
        }

        return dp[m - 1][n - 1];
    }

    /**
     * 5. 最长回文子串
     * 二维boolean数组 倒序遍历
     *
     * @param s
     * @return
     */
    public String longestPalindrome(String s) {
        int n = s.length();
        boolean[][] dp = new boolean[n][n];
        for (int i = 0; i < n; i++) {
            dp[i][i] = true;
        }
        int result = 1, begin = 0;

        for (int i = n - 2; i >= 0; i--) {
            for (int j = i + 1; j < n; j++) {
                if (s.charAt(i) == s.charAt(j)) {
                    if (j - i == 1 || dp[i + 1][j - 1]) {
                        dp[i][j] = true;
                        if (j - i + 1 > result) {
                            result = j - i + 1;
                            begin = i;
                        }
                    }
                }
            }
        }
        return s.substring(begin, begin + result);
    }

    /**
     * 1143. 最长公共子序列
     * 一维数组解法，用一个pre变量来当做二维数组时的dp[i - 1][j - 1]使用
     *
     * @param text1
     * @param text2
     * @return
     */
    public int longestCommonSubsequence(String text1, String text2) {
        int m = text1.length(), n = text2.length();
        int[] dp = new int[n + 1];

        for (int i = 0; i < m; i++) {
            int pre = dp[0];
            for (int j = 1; j <= n; j++) {
                int cur = dp[j];
                if (text1.charAt(i) == text2.charAt(j - 1)) {
                    dp[j] = pre + 1;
                } else {
                    dp[j] = Math.max(dp[j], dp[j - 1]);
                }
                pre = cur;
            }
        }

        return dp[n];
    }

    /**
     * 718. 最长重复子数组
     * 子数组一般需要维护一个result变量，子序列一般返回dp最后一个值
     * 一维数组倒序遍历
     *
     * @param nums1
     * @param nums2
     * @return
     */
    public int findLength(int[] nums1, int[] nums2) {
        int m = nums1.length, n = nums2.length;
        int[] dp = new int[n + 1];
        int result = 0;
        for (int i = 0; i < m; i++) {
            for (int j = n; j > 0; j--) {
                if (nums1[i] == nums2[j - 1]) {
                    dp[j] = dp[j - 1] + 1;
                    result = Math.max(result, dp[j]);
                } else {
                    dp[j] = 0;
                }
            }
        }

        return result;
    }

    /**
     * 72. 编辑距离
     *
     * @param word1
     * @param word2
     * @return
     */
    public int minDistance(String word1, String word2) {
        int m = word1.length();
        int n = word2.length();
        int[] dp = new int[n + 1];

        for (int j = 1; j <= n; j++) {
            dp[j] = j;
        }

        for (int i = 1; i <= m; i++) {
            int prev = dp[0];
            dp[0] = i;
            for (int j = 1; j <= n; j++) {
                int temp = dp[j];
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    dp[j] = prev;
                } else {
                    dp[j] = Math.min(prev, Math.min(dp[j - 1], dp[j])) + 1;
                }
                prev = temp;
            }
        }

        return dp[n];
    }

    // 技巧 TODO

    /**
     * 75. 颜色分类
     * 三指针
     *
     * @param nums
     */
    public void sortColors(int[] nums) {
        int cur = 0, p1 = 0, p2 = nums.length - 1;

        while (cur <= p2) {
            if (nums[cur] == 0) {
                swap(nums, cur, p1);
                cur++;
                p1++;
            } else if (nums[cur] == 2) {
                swap(nums, cur, p2);
                p2--;
            } else {
                cur++;
            }
        }
    }

    /**
     * 31. 下一个排列
     * 技巧题
     *
     * @param nums
     */
    public void nextPermutation(int[] nums) {
        // 1. 从后向前找到第一个非递增的元素
        int i = nums.length - 2;
        while (i >= 0 && nums[i] >= nums[i + 1]) {
            i--;
        }

        // 2.如果有，从后向前找到第一个大于该元素的数，交换这两个元素
        if (i >= 0) {
            for (int j = nums.length - 1; j >= 0; j--) {
                if (nums[j] > nums[i]) {
                    swap(nums, i, j);
                    break;
                }
            }
        }

        // 3.最后将该元素后面的部分翻转
        reverse(nums, i + 1);
    }

    private void reverse(int[] nums, int left) {
        int right = nums.length - 1;
        while (left < right) {
            swap(nums, left, right);
            left++;
            right--;
        }
    }

    /**
     * 287. 寻找重复数
     * 技巧， 可以将数组索引和对应的值的关系看成链表，根据一定会出现环来计算
     *
     * @param nums
     * @return
     */
    public int findDuplicate(int[] nums) {
        // 初始化快慢指针
        int slow = nums[0];
        int fast = nums[nums[0]];

        // 寻找环内的相遇点
        while (slow != fast) {
            slow = nums[slow];
            fast = nums[nums[fast]];
        }

        // 将慢指针重置到起始位置
        slow = 0;

        // 寻找环的起点
        while (slow != fast) {
            slow = nums[slow];
            fast = nums[fast];
        }

        return slow;
    }

}

